#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Solution {
        int min_insertions(string &s, int l, int r, vector<vector<int>> &rec)
        {
                if(l == r){
                        return 0;
                }
                if(l + 1 == r){
                        return s[l] == s[r] ? 0 : 1;
                }

                if(s[l] == s[r]){
                        return rec[l][r] = min_insertions(s, l + 1, r - 1, rec);
                }

                if(rec[l][r] != -1){
                        return rec[l][r];
                }

                return rec[l][r] = min(min_insertions(s, l, r - 1, rec), min_insertions(s, l + 1, r, rec)) + 1;
        }

        int min_insertions(string &s)
        {
                int n = s.length();
                vector<vector<int>> dp(n, vector<int>(n, 0));
                for(int i = 0; i < n; i++){
                        dp[i][i] = 0;
                        if(i  < n - 1){
                                dp[i][i + 1] = s[i] == s[i + 1] ? 0 : 1;
                        }
                }

                for(int l = n - 3; l >= 0; l--){
                        for(int r = l + 2; r < n; r++){
                                if(s[l] == s[r]){
                                        dp[l][r] = dp[l + 1][r - 1];
                                }else{
                                        dp[l][r] = min(dp[l][r - 1], dp[l + 1][r]) + 1;
                                }
                        }
                        
                }

                return dp[0][n - 1];
        }
    public:
	int minInsertions(string s)
	{
                int n = s.length();
                vector<vector<int>> rec(n, vector<int>(n, -1));
                //return min_insertions(s, 0, s.length() - 1, rec);
                return min_insertions(s);
	}
};

int main()
{
	string s = "leetcode";
        cout<<Solution().minInsertions(s)<<endl;
        return 0;
}